/**
 * Created by L.jp
 * Description:将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)空间复杂度 O(1)
 * User: 86189
 * Date: 2022-05-07
 * Time: 21:48
 */
// class ListNode {
//    int val;
//    ListNode next = null;
//  }
public class Solution {
    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    /*对于指定区间反转就是翻转整个链表的进阶问题，因为要当指定区间不是整个链表时，需要断开原来的指向，然后指向新的指向
     * 所以问题比较负责，对于这个文问题，我门依然可以使用递归和迭代方法来解决
     *       对于递归：
     *               我们首先要学会翻转前n个节点，对于前n个节点的翻转，我门默认是从头结点开始翻转，头结点是第一个，那么
     *                我们从头节点的下一个节点开始，只需要不断的递归head.next，并且让n--,直到n减为1的时候，就返回
     *                就找到了第n个位置，因为我们要把链表分为两部分，前n个部分需要改变原来的指向，所以当递归到n==1时
     *                 需要记录n位置的下一个节点tmp，方便翻转后连接上这个节点，递归结束返回的节点就是翻转链表后的头结点
     *                 此时我们的头结点就是翻转部分的最后一个节点，需要改变原来的指向，即使head.next.next=head;
     *                  然后翻转后的部分连接上剩余没有反转的部分，就是head.next=temp;
     *                这就是翻转前n个节点
     *           那么对于翻转指定区间（m~n），当m==1时，就是像我们上述说的方法一样翻转即可，当m！=1的时候，我们就可以递归找到m和n的位置
     *               定义一个递归函数，从head.next开始递归翻转，让m--,n--,让m减为1的时候就可以使用上述这个翻转前n个的方法了
     *               然后让头结点拼接上翻转后返回的节点，对于n后面的节点，我们在翻转前n个的函数里面已经处理过了
     *
     *
     */
    //时间复杂度O（n) ,空间复杂度O（n)
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(m == 1){
            //m==1就找打了第m个位置，相当于反转前n个的方法
            return reverse(head,n);  //拿到反转后的新的头节点，此时后面不用反转的部分已经拼接上了
        }
        //从头结点的下一个节点开始反转，递归找到m的位置
        ListNode tmp=reverseBetween(head.next,m-1,n-1);
        //把头结点(head.next代表head后面的节点，如果有的话）到拼接上反转部分
        head.next=tmp;
        return head;
    }
    
    //反转前n个
    /**
     *
     * @param head  每一个待反转的新的头节点
     * @param n     第n个位置
     * @return      返回的是反转前n个部分后的新的头结点
     */
    ListNode end=null;
    public ListNode reverse(ListNode head,int n){
        //只有一个节点时
        if(n==1){
            //记录n的后一个位置，便于反转后拼接上
             end=head.next;
            return head;
        }
        //从头结点的下一个节点开始翻转,找到第n个位置为止
        ListNode newH=reverse(head.next,n-1);
        //递归完之后，链表反转完毕，原来的头结点还没反转
        head.next.next=head;
        //把n后面的拼接上
        head.next=end;
        return  newH;
    }
}
